package com.salim.leetcode.$18;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class FourSum {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        return kSum(nums,target,4);
    }

    public List<List<Integer>> kSum(int[] nums,int target,int k){
        List<List<Integer>> result = new ArrayList<>();
        if(k<2 || nums.length<k){
            return result;
        }
        int smallest = 0;
        int largest = 0;
        for(int i=0;i<k;i++){
            smallest+=nums[i];
            largest+=nums[nums.length-1-i];
        }
        if(smallest>target || largest<target){
            return result;
        }
        for(int x=0;x<nums.length-k+1;x++) {
            if (x == 0 || nums[x] != nums[x - 1]) {
                int current = nums[x];
                int sum = target - nums[x];
                int left = x + 1;
                int right = nums.length;
                List<List<Integer>> kResult;
                if (k - 1 == 2) {
                    kResult = twoSum(Arrays.copyOfRange(nums, left, right), sum);
                } else {
                    kResult = kSum(Arrays.copyOfRange(nums, left, right), sum, k - 1);
                }

                if (!kResult.isEmpty()) {
                    for (List<Integer> temp : kResult) {
                        List<Integer> returnResult = new ArrayList<>(temp);
                        returnResult.add(current);
                        result.add(returnResult);
                    }
                }
            }
        }
        return result;
    }

    public List<List<Integer>> twoSum(int[] nums,int sum){
        List<List<Integer>> twoSumReuslt = new ArrayList<>();
        int left = 0;
        int right = nums.length-1;
        while (left<right){
            if(nums[left]+nums[right]==sum){
                twoSumReuslt.add(Arrays.asList(nums[left],nums[right]));
                while (left<right && nums[left]==nums[left+1]){
                    left+=1;
                }
                while (right>left && nums[right-1]==nums[right]){
                    right-=1;
                }
                left+=1;
                right-=1;
            }else{
                if(nums[left]+nums[right]>sum){
                    right-=1;
                }else{
                    left+=1;
                }
            }
        }
        return twoSumReuslt;
    }

    public static void main(String[] args){
        FourSum fourSum = new FourSum();
        List<List<Integer>> result = fourSum.fourSum(new int[]{1, 0, -1, 0, -2, 2},0);
        for(List<Integer> it:result){
            System.out.println(it+" ");
        }


//        List<List<Integer>> result2 = threeSum.threeSum(new int[]{1,2,-2,-1});
//        for(List<Integer> it:result2){
//            System.out.println(it+" ");
//        }
//        List<List<Integer>> result3 = threeSum.threeSum(new int[]{1,1,-2});
//        for(List<Integer> it:result3){
//            System.out.println(it+" ");
//        }
//        List<List<Integer>> result4 = threeSum.threeSum(new int[]{0,0,0,0});
//        for(List<Integer> it:result4){
//            System.out.println(it+" ");
//        }
//        List<List<Integer>> result5 = threeSum.threeSum(new int[]{-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6});
//        for(List<Integer> it:result5){
//            System.out.println(it+" ");
//        }
//        List<List<Integer>> result6 = threeSum.threeSum(new int[]{-1,0,1,2,-1,-4});
//        for(List<Integer> it:result6){
//            System.out.println(it+" ");
//        }
    }

}
